#include<iostream>
using namespace std;

//剑指offer题13：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，是所有的奇数位于数组的前半部分，
////             所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
////   方法一：用辅助数组         方法二：两个奇数指针包夹着偶数，然后把这些偶数向后推一步，再把后面的一个奇数放到前面；重复步骤直到结束
#include<vector>
void ReSortArray(vector<int> &v)
{
	vector<int> even_store;
	even_store.reserve(v.size());
	int oddp = 0, evenp = 0;
	while (evenp < v.size())
	{
		if (v[evenp] & 0x01)//是奇数就往源数组的前面挪
			v[oddp++] = v[evenp];
		else
			even_store.push_back(v[evenp]);//否则先存起来
		++evenp;
	}
	for (size_t i = 0; i < even_store.size(); ++i)//把存在辅助数组的偶数挪回来
		v[oddp++] = even_store[i];
}
int main()
{
	int arr[] = { 0, 0, 0, 1, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 9, 1 };
	vector<int> v(sizeof(arr)/sizeof(arr[0]));
	int index = 0;
	for(;index < sizeof(arr)/sizeof(arr[0]);++index)
		v[index] = arr[index];

	ReSortArray(v);
	//for (auto &r : v)cout << r << " ";
	for(index = 0;index < v.size();++index)
		cout<< v[index] << " ";

	return 0;
}
